package structures.huffmantree;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HuffManTreeDemo {
    private static final int LENGTH = 10;
    public static void main(String[] args) {
        // 生成数据
        int[] data = new int[LENGTH];
        for (int index = 0; index < data.length; index++) {
            data[index] = (int) (Math.random() * LENGTH);
        }
        // 打印数据
        System.out.println(Arrays.toString(data));

        Node huffManTree = createHuffManTree(data);
        System.out.println("----------------------");
        System.out.println(huffManTree);
        System.out.println("----------------------");
        preOrderTree(huffManTree);
    }

    private static void preOrderTree(Node huffManTree) {
        if (huffManTree == null) {
            return;
        }

        System.out.println(huffManTree);
        preOrderTree(huffManTree.getLeftNode());
        preOrderTree(huffManTree.getRightNode());
    }

    private static Node createHuffManTree(int[] dataArray) {
       if (dataArray == null || dataArray.length == 0) {
           return null;
       }

       if (dataArray.length == 1) {
            return new Node(dataArray[0]);
       }

       List<Node> nodeList = new ArrayList<>();
        for (int data : dataArray) {
            nodeList.add(new Node(data));
        }

        while (nodeList.size() > 1) {
            nodeList.sort(null);
            Node nodeLeft = nodeList.get(0);
            Node nodeRight = nodeList.get(1);
            Node nodeParent = new Node(nodeLeft.getValue() + nodeRight.getValue());
            nodeParent.setLeftNode(nodeLeft);
            nodeParent.setRightNode(nodeRight);
            nodeList.remove(nodeLeft);
            nodeList.remove(nodeRight);
            nodeList.add(nodeParent);
        }
        return nodeList.get(0);
    }
}

// 继承 Comparable 是为了有比较方法, 被list集合包含时 可以直接用 Collections.sort 进行排序
class Node implements Comparable<Node> {
    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}


